[삽입정렬] 백준 11399번

문제

1. ATM 기 한 개가 있고, 손님들이 각자 업무를 보는 시간이 주어진다
2. 모든 손님들의 서비스를 합한 시간의 최소값을 구해라
   (사람의 수  : 1 <=  N <= 1,000)
   (사람 당 서비스 시간 :  1 <= P <= 1,000)

• 시간제한 : 1초

문제분석

1. 가장 빠른 시간에 인출하는 방법을 그리디 방식이라고 한다.
2. 시간제한은 1초 이므로, O(N^2) 이하인 정렬 알고리즘 아무거나 사용하면 된다
3. 정렬 이후 서비스 시간을 합정렬을 이용하여, 최소값 구함 그리디 방식?
    - 그리디 방식이란 탐욕법으로서 가장 최적의 해를 구하는 것을 목표하는 알고리즘이다.
    - 현재 문제에서는, 앞에 있는 손님들의 서비스 시간을 더해야하므로 반복적으로 더해지는 서비스 시간이 적어야한다
    - 따라서, 그리디 방식을 적용하여 서비스 시간의 최적의 해를 도출해야한다

슈도코드

N (사람 수)
A (공백으로 구분된 사람 당 서비스 시간)
for( A 크기 ){
    arr(A배열 저장)
}
 
for(i : N만큼 반복){
    for( 정렬된 범위 ){
        삽입할 위치 찾기
    }
    
    shift(정렬된 범위에 삽입할 위치에 삽입하기)
}
 
for( arr 배열 ){
    for( 합정렬 ){
        최소값 구하기;
    }
}
 
출력

구현하기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Integer size = Integer.parseInt(bf.readLine());
        
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int []arr = new int[size];
        
        for (int i =0; i< size; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        for (int i = 1; i< arr.length; i++){
            int insertIndex = i;
            for (int j = i - 1; j >= 0; j--){
                if( arr[j] >= arr[i] ){
                    insertIndex = j;
                }
            }
 
            shift(arr, insertIndex, i);
        }
     
        int min = 0;
        for (int i =0; i< arr.length; i++) {
            for (int j = 0; j <= i; j++){
                min += arr[j];
            }
        }
 
        System.out.println(min);
    }
 
    private static void shift(int[] arr, int insertIndex, int endIndex){
        int temp = arr[endIndex];
 
        for (int i = endIndex; i > insertIndex; i--){
            arr[i] = arr[i-1];
        }
 
        arr[insertIndex] = temp;
    }
 
    
 
}

---

관련 문서

• [정렬] 삽입정렬 — 이 문제에 적용된 삽입정렬 개념 설명